package com.sheng.leetcode.year2022.month08.day23;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author liusheng
 * @date 2022/08/23
 *
 * 782. 变为棋盘
 *
 * 一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能任意交换两列或是两行的位置。
 * 返回 将这个矩阵变为  “棋盘”  所需的最小移动次数 。如果不存在可行的变换，输出 -1。
 * “棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。
 *
 * 示例 1:
 * 输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
 * 输出: 2
 * 解释:一种可行的变换方式如下，从左到右：
 * 第一次移动交换了第一列和第二列。
 * 第二次移动交换了第二行和第三行。
 *
 * 示例 2:
 * 输入: board = [[0, 1], [1, 0]]
 * 输出: 0
 * 解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.
 *
 * 示例 3:
 * 输入: board = [[1, 0], [1, 0]]
 * 输出: -1
 * 解释: 任意的变换都不能使这个输入变为合法的棋盘。
 *
 * 提示：
 *
 * n == board.length
 * n == board[i].length
 * 2 <= n <= 30
 * board[i][j] 将只包含 0或 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/transform-to-chessboard
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0782 {

    @Test
    public void test01() {
        int[][] board = {{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}};
//        int[][] board = {{0, 1}, {1, 0}};
//        int[][] board = {{1, 0}, {1, 0}};
        System.out.println(new Solution().movesToChessboard(board));
//        System.out.println(0^0^0^0);
//        System.out.println(1^1^1^1);
//        System.out.println(0^0^1^1);
//        System.out.println(0^1^1^1);
    }
}
class Solution {
    int length;
    Map<String, Integer> map;
    public int movesToChessboard(int[][] board) {
        // 思路：保证数组元素个数正确的情况下，对首行和首列进行排序，保证棋盘即可
        // 要求：保证010101或者101010，奇数时，保证0和1的数量相差1，偶数时，保证0和1的数量相等
        length = board.length;

//        map = new HashMap<>();
//        for (int i = 0; i < length; i++) {
//            map.put(Arrays.toString(board[i]), map.getOrDefault(Arrays.toString(board[i]), 0) + 1);
//        }
//        if (map.size() > 2) {
//            return -1;
//        }
//        if (map.size() == 1) {
//            return -1;
//        }
//        String[] strings = new String[2];
//        int[] ints = new int[2];
//        int index = 0;
//        Set<Map.Entry<String, Integer>> entries = map.entrySet();
//        for (Map.Entry<String, Integer> entry : entries) {
//            strings[index] = entry.getKey();
//            ints[index] = entry.getValue();
//            index++;
//        }
//        if (Math.abs(ints[0] - ints[1]) <= 1) {
//            for (int i = 0; i < 2; i++) {
//                int n0 = 0;
//                int n1 = 1;
//                String[] split = strings[i].substring(1, strings[i].length() - 1).split(", ");
//                int[] intss = Arrays.stream(split).mapToInt(Integer::parseInt).toArray();
//                for (int i1 = 0; i1 < length; i1++) {
//                    if (intss[i1] == 0) {
//                        n0++;
//                    } else {
//                        n1++;
//                    }
//                }
//                if (Math.abs(n0 - n1) > 1) {
//                    return -1;
//                }
//            }
//        }

        // 在数组的任意一个矩形中，四个顶点一定都为1或都为0或2个为1,2个为0，否则数据格式就是错误
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                /**
                 * System.out.println(0^0^0^0); //0
                 * System.out.println(1^1^1^1); //0
                 * System.out.println(0^0^1^1); //0
                 * System.out.println(0^1^1^1); //1
                 * System.out.println(0^0^0^1); //1
                 */
                if ((board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) != 0) {
                    return -1;
                }
            }
        }
        // rowSum：记录首行数组中，1的数量
        // colSum：记录首列数组中，1的数量
        // rowSum：记录首行数组中，与101010这种顺序不同的元素的数量
        // rowSum：记录首列数组中，与101010这种顺序不同的元素的数量
        int rowSum = 0, colSum = 0, rowDiff = 0, colDiff = 0;
        for (int i = 0; i < length; i++) {
            rowSum += board[0][i];
            colSum += board[i][0];
            rowDiff += board[0][i] == i % 2 ? 1 : 0;
            colDiff += board[i][0] == i % 2 ? 1 : 0;
        }
        // 数组中的元素里，0和1的数量都只有两种可能，在length为偶数时，数量为length / 2；在length为奇数时，数量为(length + 1) / 2
        // 判断首行数组中1元素的数量是否符合要求
        if (rowSum < length / 2 || (length + 1) / 2 < rowSum) {
            return -1;
        }
        // 判断首列数组中1元素的数量是否符合要求
        if (colSum < length / 2 || (length + 1) / 2 < colSum) {
            return -1;
        }
        // 计算行和列分别要修改的次数
        // 10101
        // 数组长度为奇数时
        if (length % 2 == 1) {
            // 错位为奇数个
            if (rowDiff % 2 == 1) {
                // 转为偶数个
                rowDiff = length - rowDiff;
            }
            // 错位为奇数个
            if (colDiff % 2 == 1) {
                // 转为偶数个
                colDiff = length - colDiff;
            }
        } else {
            rowDiff = Math.min(length - rowDiff, rowDiff);
            colDiff = Math.min(length - colDiff, colDiff);
        }
        // 此时rowDiff为要修改的行数的次数，colDiff为要修改的列数的次数
        // 每交换1次会修改2个错位
        return (rowDiff + colDiff) / 2;
    }
}
